Amit’s A* Pages

The problem we’re trying to solve is to get a game object from the starting point to a goal. Pathfinding addresses the problem of finding a good path from the starting point to the goal—avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.). Movement addresses the problem of taking a path and moving along it. It’s possible to spend your efforts on only one of these. At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm would find a path when the object begins to move and the object would follow that path, oblivious to everything else. At the other extreme, a movement-only system would not look ahead to find a path (instead, the initial “path” would be a straight line), but instead take one step at a time, considering the local environment at every point. Best results are achieved by using both pathfinding and movement algorithms.

Pathfinding#

1. Introduction to A*
   1. Algorithms
   2. Dijkstra’s Algorithm and Best-First-Search
   3. The A* Algorithm
2. Heuristics
   1. A*’s Use of the Heuristic
   2. Speed or accuracy?
   3. Scale
   4. Exact heuristics
      1. Precomputed exact heuristic
      2. Linear exact heuristic
   5. Heuristics for grid maps
      1. Manhattan distance
      2. Diagonal distance
      3. Euclidean distance
      4. Euclidean distance, squared
      5. Multiple goals
      6. Breaking ties
   6. Approximate heuristics
3. Implementation notes
   1. Sketch
      1. Connectivity
   2. Performance
   3. Source code and demos
      1. Demos
      2. Code
   4. Set representation
      1. Unsorted arrays or linked lists
      2. Sorted arrays
      3. Binary heaps
      4. Sorted skip lists
      5. Indexed arrays
      6. Hash tables
      7. Splay trees
      8. Bucketing
      9. HOT queues
      10. Pairing heaps
      11. Soft heaps
      12. Sequence heaps
      13. Data Structure Comparison
      14. Hybrid representations
   5. Interaction with the game loop
      1. Early exit
      2. Interruptible algorithm
      3. Group movement
      4. Refinement
4. Variants of graph search
   1. Flow fields
   2. Beam search
   3. Iterative deepening
   4. Weighted A*
   5. Bandwidth search
   6. Bidirectional search
   7. Dynamic A* and Lifelong Planning A*
   8. Jump Point Search
   9. Any angle movement
   10. Other variants
5. Dealing with moving obstacles
   1. Recalculating paths
   2. Path splicing
   3. Watching for map changes
   4. Predicting obstacle movement
6. Space used by precalculated paths
   1. Locations vs. directions
   2. Path compression
      1. Location storage
      2. Direction storage
   3. Computed waypoints
   4. Limited path length
   5. Summary

Other topics#

There are many other topics related to pathfinding.

1. Map representations
   1. Grids
      1. Tile movement
      2. Edge movement
      3. Vertex movement
   2. Polygonal maps
      1. Managing complexity
   3. Navigation Meshes
      1. Polygon movement
      2. Polygon edge movement
      3. Polygon vertex movement
      4. Hybrid movement
      5. Path smoothing
   4. Hierarchical
   5. Wraparound maps
   6. Connected Components
   7. Road maps
   8. Skip links
   9. Waypoints
   10. Graph Format Recommendations
2. Long and short term goals
   1. Unit movement
   2. Behavior flags or stacks
   3. Waiting for movement
   4. Coordinated movement
3. Movement costs for pathfinders
   1. Altitude
      1. Moving uphill
      2. Moving up- or downhill
   2. Terrain
      1. Forests, mountains, and hills
      2. Roads
      3. Walls or other barriers
      4. Sloped Land
   3. Enemies and friendly units
   4. Marked beacons
   5. Fuel consumption
4. User experience with shortest paths
   1. Dumb movement
   2. Smart movement
   3. Multithreading
   4. Multiple units
   5. Multiple waypoints
5. Applications
   1. Exploration
   2. Spying
   3. Road building
   4. Terrain analysis
   5. City building
6. AI techniques
   1. Neural Networks
   2. Genetic Algorithms
   3. Reinforcement Learning
7. References